#define _CRT_SECURE_NO_WARNINGS 1
//https://leetcode.cn/problems/count-pairs-of-connectable-servers-in-a-weighted-tree-network/
class Solution {
public:
    typedef pair<int, int> PII;
    int dfs(int u, int fa, vector<vector<PII>>& g, int signalSpeed, int sum) {
        int cnt = sum % signalSpeed == 0;
        for (auto it : g[u]) {
            int v = it.first;
            int w = it.second;
            if (v != fa) {
                cnt += dfs(v, u, g, signalSpeed, sum + w);
            }
        }
        return cnt;
    }


    vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
        int n = edges.size() + 1;
        vector<vector<PII>> g(n);
        for (auto it : edges) {
            int a = it[0], b = it[1], w = it[2];
            g[a].push_back({ b,w });
            g[b].push_back({ a,w });
        }
        vector<int>ans(n);
        for (int i = 0; i < n; i++) {
            int s = 0;
            for (auto it : g[i]) {
                int u = it.first;
                int w = it.second;
                int cnt = dfs(u, i, g, signalSpeed, w);
                ans[i] += s * cnt;
                s += cnt;
            }
        }
        return ans;
    }
};